package org.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

/**
 * 338. 比特位计数
 *
 * 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 *
 * 示例 1:
 *
 * 输入: 2
 * 输出: [0,1,1]
 *
 * 示例2:
 *
 * 输入: 5
 * 输出: [0,1,1,2,1,2]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/counting-bits
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class BitSolution {

    public int[] countBits(int num) {
        if (num < 0) {
            return null;
        }
        List<Integer> resultList = new ArrayList<>(num);
        for (int index = 0; index <= num; index ++) {
            resultList.add(getBitCount(index));
        }
        return list2Array(resultList);
    }

    private Integer getBitCount(Integer num) {
        List<Integer> bitList = new ArrayList<>();
        // 被除数
        int c1 = num;
        // 余数
        int c2;
        do {
            int temp = c1 / 2;
            c2 = c1 % 2;
            bitList.add(c2);
            c1 = temp;
        } while (c1 != 0);
        int count = 0;
        for (Integer value : bitList) {
            if (Objects.equals(value, 1)) {
                count++;
            }
        }
        return count;
    }

    private int[] list2Array(List<Integer> resultList) {
        int[] array = new int[resultList.size()];
        for (int index = 0; index < resultList.size(); index ++) {
            array[index] = resultList.get(index);
        }
        return array;
    }

    public static void main(String[] args) {
        BitSolution bitSolution = new BitSolution();
        int[] countBits = bitSolution.countBits(5);
        System.out.println(Arrays.toString(countBits));
    }
}
